/* ================================================================
*   Copyright (C) 2020 All rights reserved.
*
*   文件名称：xhashmap.h
*   创 建 者：xunmenglong
*   创建日期：2020年08月05日
*   描    述：一个多线程读，单线程写的hashmap，追求极致的读性能, 读不加锁
*
================================================================ */


#ifndef XHASHMAP_H_
#define XHASHMAP_H_

#include <list>
#include <deque>
#include <functional>

#include "bthread/bthread.h"

#include "xutil.h"
#include "xhash.h"

using namespace xutil;

// 字节对齐, 不能删除, 删除之后load索引的效率会变得很低
#pragma pack(4)
template<class _K,
    class _V,
    class _HashFun = xhash<_K>,
    class _Equal = std::equal_to<_K>>
class xhashmap {
#define XHASH_DEFAULT_BUCKET_NUM 1000
#define XHASH_MIN_DELAY_QUEUE_LEN 1000
#define XHASH_DELAY_TIME 10000

 public:
    typedef _V value_t;
    typedef _K key_t;

 private:
    // 桶内最小存储单元, 按列表存储
    struct node_t {
        key_t key;
        value_t value;
        struct node_t * next;
    };
    // hash桶
    struct bucket_t {
        node_t * first;
    };
    // 删除节点信息, 增加删除时间信息
    struct del_node_t {
        node_t * node;
        struct timeval time;
    };

 private:
    _HashFun _hashfun;
    _Equal _equal;

    int _bucket_num;                    // hash桶数量
    int _bucket_exp;                    // 用于取代算桶的%函数, 用位移替代
    bthread_mutex_t _w_lock;            // 写锁
    bucket_t *_buckets = NULL;          // 桶列表
    list<del_node_t> _delay_queue;      // 延时删除的队列
    node_t * _free_node = NULL;         // 延时队列中释放出来的空闲node
    deque<node_t *> _blocks;            // 所有分配出来的block
    node_t * _cur_block = NULL;         // 当前正在分配的block
    int _cur_block_node = 0;            // 当前block分配到第几个了
    int _block_size = 0;                // 每个block包含多少个node_t
    int _node_size = 0;                 // 包含元素个数

 public:
    xhashmap() {}
    ~xhashmap() {}

    int init(int bucket_num = XHASH_DEFAULT_BUCKET_NUM) {
        // 首先计算真正的桶数量, 为2的指数
        _bucket_num = 2;
        _bucket_exp = 1;
        while (_bucket_num < bucket_num) {
            _bucket_num = _bucket_num << 1;
            _bucket_exp++;
        }

        if (bthread_mutex_init(&_w_lock, NULL)) {
            LOG(ERROR) << "init write lock fail";
            return -1;
        }

        _buckets = (bucket_t *)calloc(1, sizeof(bucket_t)*_bucket_num);
        if (_buckets == NULL) {
            LOG(ERROR) << "malloc _buckets fail";
            return -1;
        }

        _block_size = _bucket_num;
        return 0;
    }

    inline int size() {
        return _node_size;
    }

    inline node_t * _get_first_node(const key_t key) {
        size_t hashcode = _hashfun(key);
        int bucket_idx = hashcode - (hashcode >> _bucket_exp << _bucket_exp);
        return _buckets[bucket_idx].first;
    }

    inline bucket_t * _get_bucket(const key_t key) {
        size_t hashcode = _hashfun(key);
        int bucket_idx = hashcode - (hashcode >> _bucket_exp << _bucket_exp);
        return &(_buckets[bucket_idx]);
    }

    int set(const key_t key, const value_t value, bool is_change = true) {
        // 整个写过程加锁
        LockUtil l(&_w_lock);

        // 首先尝试清空超时节点
        _free_delete_node();

        bucket_t * bucket = _get_bucket(key);
        node_t * first_node = bucket->first;

        node_t * curr_node = first_node;
        while (curr_node) {
            if (_equal(curr_node->key, key)) {
                if (is_change) {
                    curr_node->value = value;
                    return 0;
                } else {
                    return 1;
                }
            }
            curr_node = curr_node->next;
        }

        // key值不存在, 需要插入节点
        // 插入最前面, 大部分场景新插入的数据被访问的概率较高
        node_t * new_node = _alloc_node();
        if (new_node == NULL) {
            LOG(ERROR) << "malloc node_t fail";
            return -1;
        }
        new_node->key = key;
        new_node->value = value;
        new_node->next = first_node;
        bucket->first = new_node;
        _node_size++;
        return 0;
    }

    value_t * get(const key_t key) {
        node_t * curr_node = _get_first_node(key);

        while (curr_node) {
            if (_equal(curr_node->key, key)) {
                return &(curr_node->value);
            }
            curr_node = curr_node->next;
        }
        // 没找到, 但是key值不存在
        return NULL;
    }

    int remove(const key_t key) {
        LockUtil l(&_w_lock);

        bucket_t * bucket = _get_bucket(key);
        node_t * curr_node = bucket->first;
        node_t * last_node = NULL;

        while (curr_node) {
            if (_equal(curr_node->key, key)) {
                if (last_node == NULL) {
                    bucket->first = curr_node->next;
                } else {
                    last_node->next = curr_node->next;
                }
                // 然后将当前curr_node加入延时队列
                struct timeval nowtime;
                gettimeofday(&nowtime, NULL);

                del_node_t del_node;
                del_node.node = curr_node;
                del_node.time = nowtime;

                _delay_queue.push_back(del_node);
                _node_size--;
                return 0;
            }
            last_node = curr_node;
            curr_node = curr_node->next;
        }
        // 没找到, 不报错
        return 1;
    }

    int _free_delete_node() {
        if (_delay_queue.size() <= XHASH_MIN_DELAY_QUEUE_LEN) {
            // 删除队列积累不够多, 直接退出
            return 0;
        }

        // 从前开始往后遍历
        struct timeval nowtime;
        gettimeofday(&nowtime, NULL);
        while (true) {
            if (_delay_queue.size() == 0) {
                // 已经遍历完了
                return 0;
            }
            del_node_t del_node = _delay_queue.front();
            if (TIMEDIFF(del_node.time, nowtime) >= XHASH_DELAY_TIME) {
                // 可以回收了
                del_node.node->next = _free_node;
                _free_node = del_node.node;
                _delay_queue.pop_front();
            } else {
                // 当前节点还没超过时间, 直接返回了
                return 0;
            }
        }
        return 0;
    }

    node_t * _alloc_node() {
        // 空闲列表中还有节点
        if (_free_node != NULL) {
            node_t * ret_node = _free_node;
            _free_node = _free_node->next;
            return ret_node;
        }

        // 从block中分配
        if (_blocks.size() == 0 || _cur_block_node >= _block_size) {
            // 首次分配 或者 当前块已经分配完了
            node_t * block = _alloc_block();
            if (block == NULL) {
                LOG(ERROR) << "alloc block fail";
            }
            _blocks.push_back(block);
            // 重置当前block的信息
            _cur_block = block;
            _cur_block_node = 0;
        }
        return &(_cur_block[_cur_block_node++]);
    }

    node_t * _alloc_block() {
        return (node_t *)calloc(1, sizeof(node_t)*_block_size);
    }
};

#pragma pack()

#endif  // XHASHMAP_H_
